package leetcode.median;

import leetcode.base.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * ClassName: $655_PrintBinaryTree
 * Description:
 * date: 2021-10-18 21:12
 *
 * @author liyifan
 */
public class $655_PrintBinaryTree {
    public List<List<String>> printTree(TreeNode root) {
        int height = getHeight(root);
        String[][] res = new String[height][(int)Math.pow(2, height) - 1];
        for (String[] s:res) {
            Arrays.fill(s, "");
        }
        List<List<String>> ans = new ArrayList<>();
        fill(res, root, 0, 0, res[0].length);
        for (String[] s:res) {
            ans.add(Arrays.asList(s));
        }
        return ans;
    }

    public void fill(String[][] res, TreeNode root,int i, int left, int right){
        if (root == null)
            return;
        res[i][(left + right) / 2] = String.valueOf(root.val);
        fill(res, root.left, i + 1, left, (left + right) / 2);
        fill(res, root.right, i + 1, (left + right + 1) / 2, right);
    }

    public int getHeight(TreeNode root) {
        if (root == null)
            return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }
}
